package listbyorder.access001_100.test19;

import listbyorder.utils.ListNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/28 13:06
 */
public class Solution3 {

    // 只需要遍历一次链表的解法
    // 首先定义两个指针
    // 快指针首先走n步
    // 然后快慢指针一起向后走
    // 等到快指针走到null的时候
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;
        }
        //两个指针同时走
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}
